package com.wc.alorithm_blue_bridge._数学知识.快速幂.Q1138;

import java.util.Scanner;

/**
 * @Author congge
 * @Date 2023/11/8 14:57
 * @description
 * 数列
 * https://www.lanqiao.cn/problems/1138/learning/?page=1&first_category_id=1&sort=students_count&tags=%E5%B7%AE%E5%88%86
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();
        int k = sc.nextInt();
        int m = sc.nextInt();
        int p = sc.nextInt();
        Main main = new Main();
        System.out.println(main.quickMin(m, k + 1, p));
    }

    public long quickMin(int n, int k, int p) {
        if (k == 1) {
            return n % p;
        }
        long qk = quickMin(n, k / 2, p) % p;
        long ans = qk * qk % p;

        if ((k & 1) == 1) {
            ans = ans * n % p;
        }
        return ans % p;
    }
}
